/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package gamaze;

import java.util.Stack;

/**
 * Creates a random restriction map.
 * @author pborrego
 */
public class MazeGen {
    protected int width, height;
    protected int[] maze;
    public final static int RANDOM = 0;

    public MazeGen(int w, int h)
    {
        this.width = w;
        this.height = h;
        maze = new int[this.width * this.height];
    }

    /**
     * This does not guarantee a maze that is solvable.
     */
    public void generate(int type)
    {
        if(type == MazeGen.RANDOM)
        {
            for(int i=0; i<(this.width * this.height); i++)
            {
                maze[i] = (int)(Math.random()*16);
            }
        }
    }

    /**
     * creates a maze using the depth first search technique.
     */
    public void dfsMaze()
    {
        int vmask = 16;
        int unvisted[];
        Stack<Integer> previous = new Stack<Integer>();
        int current = (int)(Math.random() * (width * height));
        int next;

        // initalize the maze
        for(int i=0; i<(this.width * this.height); i++)
        {
            this.maze[i] = vmask;
        }

        for(int i=(width * height); i>0; i--)
        {
            if((this.maze[current] & vmask) == vmask)
                this.maze[current] ^= vmask;    // sets the visited bit to 0
            
            unvisted = unvistedNeighbors(current);
            if(unvisted.length > 0)
            {
                next = unvisted[(int)(Math.random() * unvisted.length)];
                removeWall(current, next);
                previous.push(new Integer(current));
                current = next;
            }
            else
            {
                if(!previous.empty())
                {
                    current = previous.pop().intValue();
                    i++;
                }
            }
        }
    }

    /**
     *
     * @param center is the index of the cell whose neighbors we are trying to
     * find.
     * @return an array of all the neighbor'stck indexes that have not been
     * visited.
     */
    private int[] unvistedNeighbors(int center)
    {
        int vmask = 16;
        Stack<Integer> stck = new Stack<Integer>();
        int n = 0, e = 0, s = 0, w = 0;
        int[] results;

        // This section gets the neighbor's indexes
        n = center - this.width;
        e = center + (((center % this.width) == (this.width - 1)) ? -(center + 1) : 1);
        s = (center + this.width) > ((this.width * this.height) - 1) ? -1 : (center + this.width);
        w = center + (((center % this.width) == 0) ? -(center + 1) : -1);

        // each if statement determines if the index is valid and has not been
        // visited yet.
        if(n >= 0 && (this.maze[n] & vmask) == vmask)
            stck.push(new Integer(n));

        if(e >= 0 && (this.maze[e] & vmask) == vmask)
            stck.push(new Integer(e));

        if(s >= 0 && (this.maze[s] & vmask) == vmask)
            stck.push(new Integer(s));

        if(w >= 0 && (this.maze[w] & vmask) == vmask)
            stck.push(new Integer(w));

        // Transfer the stack data to an array format
        results = new int[stck.size()];

        for(int i=0; i<results.length; i++)
            results[i] = stck.pop().intValue();

        return results;
    }

    /**
     * Takes too cells and removes the wall common to them.
     * This assumes that the two cells are adjacent to each other.
     * @param c is the first index of the cell.
     * @param c2 is the second index of the cell.
     */
    private void removeWall(int c, int c2)
    {
        int n = 1, e = 2, s = 4, w = 8;
        int dis;

        dis = c - c2;

        if(dis == 1)
        {
            maze[c] ^= w;
            maze[c2] ^= e;
        }

        if(dis == -1)
        {
            maze[c] ^= e;
            maze[c2] ^= w;
        }

        if(dis == this.width)
        {
            maze[c] ^= n;
            maze[c2] ^= s;
        }

        if(dis == -this.width)
        {
            maze[c] ^= s;
            maze[c2] ^= n;
        }
    }

    /**
     * @return the maze
     */
    public int[] getMaze() {
        return maze;
    }
}
